package dp;

public class _09_416_分割等和子集 {
	// 01背包问题核心：用该元素 与 不同该元素，该元素只能用一次
	// 二维解法在leetcode上会超时
    public static boolean canPartition(int[] nums) {
    	int N = 10010;
    	int sum = 0;
    	int dp[][] = new int[N][N];
    	for(int i = 0; i < nums.length; i++) {
    		sum += nums[i];
    	}
    	// 奇数直接返回false
    	if(sum % 2 == 1) {
    		return false;
    	}
    	int mid = sum/2;
    	// dp下标是从1开始，数组下标是从0开始，所以下面的nums都需要i-1
    	for(int i = 1; i <= nums.length; i++) {
    		for(int j = 1; j <= mid; j++) {
    			if(nums[i-1] > j) {
    				dp[i][j] = dp[i-1][j];
    			} else {
    				dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i-1]] + nums[i-1]);
    			}
    			
    			if(dp[i][j] == mid) {
    				return true;
    			}
    			
    		}
    	}
    	
    	return false;
    }
    
    public static void main(String[] args) {
    	int[] nums = {1,2,3,5};
    	System.out.println(canPartition(nums));
	}
}
